package rsa.lib;

import java.math.BigInteger;
import java.security.SecureRandom;

public class PrimeLib {
	public static BigInteger [] getqm(BigInteger p)
	{
		p = p.subtract(BigInteger.ONE);
		BigInteger two = new BigInteger("2");
		BigInteger neg = new BigInteger("-1");
		BigInteger [] rt ={BigInteger.ZERO, BigInteger.ZERO}; // rt = {q, m}
		if (p.mod(two).compareTo(BigInteger.ZERO) != 0)
		{
			rt[0] = neg; rt[1] = neg;
			return rt;
		}
		BigInteger divisor = p.divide(two);
		BigInteger counter = BigInteger.ONE;
		//double maxq = (Math.log(p))/(Math.log(2));
		while (/*count <= maxq && */divisor.mod(two).compareTo(BigInteger.ZERO)==0)
		{
			counter = counter.add(BigInteger.ONE);
			divisor = divisor.divide(two);
		}
		rt[0] = counter; rt[1] = divisor;
		return rt;
	}
	
	public static int Miller(BigInteger pval)
	{
		BigInteger [] qandm = getqm(pval);
		BigInteger qval =qandm[0];
		BigInteger neg = new BigInteger("-1");
		if (qval.compareTo(neg)==0)return 0;

		SecureRandom r = new SecureRandom();
		BigInteger bval = new BigInteger(pval.bitLength(),r);
		
		
		BigInteger mval =qandm[1];
		BigInteger two = new BigInteger("2");
		
		BigInteger pminusone = pval.subtract(BigInteger.ONE);

			
		if (bval.modPow(mval,pval).compareTo(BigInteger.ONE)==0)return 1;
		BigInteger j = BigInteger.ZERO;
		BigInteger indexval = mval;
		while (j.compareTo(qval)<0)
		{
			if (pminusone.compareTo(bval.modPow(indexval,pval))==0)return 1;
			indexval = indexval.multiply(two);
			j = j.add(BigInteger.ONE);			
		}
		return 0;
	}
	
	public static BigInteger createPrime(int bitlength, int numTests)
	{
		
		SecureRandom r = new SecureRandom();
		//return new BigInteger(bitlength, 200, r);
		BigInteger p = new BigInteger(bitlength,r);
		BigInteger two = new BigInteger("2");
		
		if((p.mod(two)).compareTo(BigInteger.ZERO) == 0)
			p = p.add(BigInteger.ONE);
		
		int h = 0;
		
		while(h < numTests)
		{
			if(Miller(p)==0){
				h = 0;
				p = p.add(two);
			}
			else h++;
		}
		return p;
	}
	
	public static BigInteger pow(BigInteger base, BigInteger exponent, BigInteger modulus){
		BigInteger result = BigInteger.ONE;
		while (exponent.compareTo(BigInteger.ZERO) > 0){
			if((exponent.and(BigInteger.ONE)).compareTo(BigInteger.ONE) == 0)
				result = (result.multiply(base)).mod(modulus);
			exponent = exponent.shiftRight(1);
			base = (base.multiply(base)).mod(modulus);
		}
		return result;
	}
	
	public static int bitLength(BigInteger in){
		int result = 0;
		while(in.compareTo(BigInteger.ZERO) > 0){
			in = in.shiftRight(1);
			result++;
		}
		return result;
	}
	
	public static void main(String[] args){
		BigInteger p1 = createPrime(500, 100);
		BigInteger p2 = createPrime(500, 100);
		//BigInteger p = pow(new BigInteger("100"), new BigInteger("10"), new BigInteger("51"));
		System.out.println(p1.multiply(p2));
	}
}
